#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace ly
{
	enum color {
		RED,
		BLACK
	};
	template<class T>
	struct Node {
		Node* left, * right, * parent;
		T value;
		color c;
		Node(const T& v = T())
			:value(v)
		{
			left = right = parent = nullptr;
			c = RED;
		}
	};
	template<class T,class ref,class ptr>
	class iterator {
	public:
		typedef Node<T> Node;
		iterator(Node* v = nullptr) {
			_data = v;
		}
		iterator(const iterator& a) {
			_data = a._data;
		}
		iterator operator=(const iterator a) {
			_data = a._data;
			return _data;
		}
		iterator operator++() {
			if (_data == nullptr) {
				assert(0);
			}
			if (_data->right != nullptr) {
				_data = _data->right;
				while (_data->left != nullptr) {
					_data = _data->left;
				}
			}
			else {
				if (_data == _data->parent->left) {
					_data = _data->parent;
				}
				else {
					while (_data->parent != nullptr && _data == _data->parent->right) {
						_data = _data->parent;
					}
					_data = _data->parent;
				}
			}
			return _data;
		}
		iterator operator++(int) {
			if (_data == nullptr) {
				assert(0);
			}
			T p = *_data;
			++(*this);
			return p;
		}
		iterator operator--() {
			if (_data == nullptr) {
				assert(0);
			}
			if (_data->left != nullptr) {
				_data = _data->left;
				while (_data->right != nullptr) {
					_data = _data->right;
				}
			}
			else {
				if (_data == _data->parent->right) {
					_data = _data->parent;
				}
				else {
					while (_data->parent != nullptr && _data == _data->parent->left) {
						_data = _data->parent;
					}
					_data = _data->parent;
				}
			}
			return _data;
		}
		iterator operator--(int) {
			if (_data == nullptr) {
				assert(0);
			}
			T p = *_data;
			--(*this);
			return p;
		}
		bool operator==(const iterator& a) const {
			return _data == a._data;
		}
		bool operator!=(const iterator& a) const {
			return _data != a._data;
		}
		ref operator*() {
			if (_data == nullptr) {
				assert(0);
			}
			return _data->value;
		}
		ref operator->() {
			if (_data == nullptr) {
				assert(0);
			}
			return _data->value;
		}
		Node* _data;
	};
	template<class key,class T,class KeyofT>
	class rbtree{
	public:
		typedef Node<T> Node;
		typedef ly::iterator<T,T&,T*> iterator;
		typedef ly::iterator<T,const T&,const T*> const_iterator;
		KeyofT kt;
		rbtree() {
			root = nullptr;
			_size = 0;
		}
		~rbtree() {
			DeleteRbtree(root);
		}
		iterator begin() {
			Node* t = root;
			while (t->left != nullptr) {
				t = t->left;
			}
			return t;
		}
		iterator end() {
			return nullptr;
		}
		const_iterator ConstBegin() const 
		{
			Node* t = root;
			while (t->left != nullptr) {
				t = t->left;
			}
			return t;
		}
		const_iterator ConstEnd() const 
		{
			return nullptr;
		}
		Node* insert(const T& kv) {
			if (root == nullptr) {
				Node* t = new Node(kv);
				assert(t);
				root = t; root->c = BLACK;
				_size++;
				return root;
			}
			else {
				Node* t = root,* next=root;
				while (next) {
					if (kt(kv) < kt(next->value)) {
						t = next;
						next = next->left;
					}
					else if (kt(kv) == kt(next->value)) {
						return next;
					}
					else {
						t = next;
						next = next->right;
					}
				}
				Node* NewNode = new Node(kv);
				if (kt(kv) < kt(t->value)) {
					t->left = NewNode;
					NewNode->parent = t;
				}
				else {
					t->right = NewNode;
					NewNode->parent = t;
				}
				if (t->c == BLACK) {
					NewNode->c = RED;
					_size++;
					return NewNode;
				}
				else {
					Node* p = t->parent,*tt=NewNode;
					while (true) {
						if (t == p->left) {
							if (p->right != nullptr) {
								if (p->right->c == RED) {
									ChangeColor(p);
								}
								else {
									if (tt == t->left) {
										RRotate(t);
										t->c = BLACK;
										p->c = RED;
									}
									else {
										LRotate(tt);
										RRotate(tt);
										tt->c = BLACK;
										p->c = RED;
									}
									break;
								}
							}
							else {
								if (tt == t->left) {
									RRotate(t);
									t->c = BLACK;
									t->left->c = t->right->c = RED;
								}
								else {
									LRotate(tt);
									RRotate(tt);
									tt->c = BLACK;
									tt->left->c = tt->right->c = RED;
								}
								break;
							}
						}
						else {
							if (p->left != nullptr) {
								if (p->left->c == RED) {
									ChangeColor(p);
								}
								else {
									if (tt == t->right) {
										LRotate(t);
										t->c = BLACK;
										p->c = RED;
									}
									else {
										RRotate(tt);
										LRotate(tt);
										tt->c = BLACK;
										p->c = RED;
									}
									break;
								}
							}
							else {
								if (tt == t->right) {
									LRotate(t);
									t->c = BLACK;
									t->left->c = t->right->c = RED;
								}
								else {
									RRotate(tt);
									LRotate(tt);
									tt->c = BLACK;
									tt->left->c = tt->right->c = RED;
								}
								break;
							}
						}
						if (p->parent == nullptr || p->parent->parent == nullptr || p->parent->c == BLACK) {
							break;
						}
						tt = p; t = p->parent; p = t->parent;
					}
					root->c = BLACK;
				}
				_size++;
				return NewNode;
			}
		}
		void ChangeColor(Node* p) {
			p->left->c = p->right->c = BLACK;
			p->c = RED;
		}
		void RRotate(Node* p) {
			Node* child = p->left, *pp = p->parent;
			if (pp->parent != nullptr) {
				if (pp == pp->parent->left) {
					pp->parent->left = p;
				}
				else {
					pp->parent->right = p;
				}
			}
			else {
				root = p;
			}
			p->parent = pp->parent;
			pp->left = p->right;
			if (p->right != nullptr) {
				p->right->parent = pp;
			}
			p->right = pp; 
			pp->parent = p; 
		}
		void LRotate(Node* p){
			Node* child = p->right,*pp=p->parent;
			if (pp->parent != nullptr) {
				if (pp == pp->parent->left) {
					pp->parent->left = p;
				}
				else {
					pp->parent->right = p;
				}
			}
			else {
				root = p;
			}
			p->parent = pp->parent;
			pp->right = p->left;
			if (p->left != nullptr) {
				p->left->parent = pp;
			}
			p->left = pp; 
			pp->parent = p; 
		}
		Node* find(key k) {
			Node* t = root;
			while (t!=nullptr&&t->value != k) {
				if (kt(t->value) > k) {
					t = t->left;
				}
				else {
					t = t->right;
				}
			}
			return t;
		}
		Node* lower_bound(const T& k) {
			Node* t = root,*id=nullptr;
			while (t) {
				if (kt(t->value) >= kt(k)) {
					id = t;
					t = t->left;
				}
				else {
					t = t->right;
				}
			}
			return id;
		}
		Node* upper_bound(const T& k) {
			Node* t = root, * id = nullptr;
			while (t) {
				if (kt(t->value) > kt(k)) {
					id = t;
					t = t->left;
				}
				else {
					t = t->right;
				}
			}
			return id;
		}
		T& operator[](const T& k) {
			Node* t = find(k);
			if (t == nullptr) {
				return insert(k)->value;
			}
			return t->value;
		}
		bool check() {
			return _check(root,BLACK);
		}
	private:
		int _check(Node* root,color c) {
			if (c == RED && root->c == RED) {
				assert(0);
			}
			int l=0,r = 0;
			if (root->left != nullptr) {
				l=_check(root->left,root->c);
			}
			std::cout << root->value << ' ';
			if (root->right != nullptr) {
				r=_check(root->right,root->c);
			}
			if (l != r) {
				assert(0);
			}
			if (root->c == BLACK) {
				return l + 1;
			}
			return l;
		}
		void DeleteRbtree(Node* root) {
			if (root->left != nullptr) {
				DeleteRbtree(root->left);
			}
			if (root->right != nullptr) {
				DeleteRbtree(root->right);
			}
			delete root;
		}
		Node* root;
		size_t _size;
	};
}